/*
 * @lc app=leetcode.cn id=1191 lang=cpp
 *
 * [1191] K 次串联后最大子数组之和
 */
#include<vector>
using namespace std;
// @lc code=start
class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        int sum = this->sum(arr);
        if (k>=2){
            int arr_len=arr.size();
            for (int i=0;i<arr_len;++i){
                arr.push_back(arr[i]);
            }
        }
        int max_sum=0;
        int s=0;
        for (int i=0;i<arr.size();i++){
            s=s>0?s+arr[i]:arr[i];
            if (s>max_sum){
                max_sum=s;
            }
        }
        long t =long(max(sum,0))*long((max(k-2,0)))%(1000000000+7);
        return (max_sum+int(t))%(1000000000+7);

    }
    inline int sum(vector<int>& arr){
        int sum=0;
        for (auto iter =arr.begin();iter!=arr.end();++iter){
            sum+=*iter;
        }
        return sum%(1000000000+7);
    }
};
// @lc code=end

